// m

// 给定一个二叉树的根节点root，树中每个节点都存放有一个0-9之间的数字，每条从根节点到叶子节点的路径都代表一个数字，例如从根节点到叶子节点的路径是1-2-3，表示数字123
// 要求：计算从根节点到叶子节点生成的所有数字的和

// 解题思路，深度优先搜索
// 深度优先搜索记录下路径上所有节点构成的数字，使用pretotal保存下当前路径上构成的数字，如果遇到叶子节点直接返回当前数字，否则递归遍历左右子树，并累加对应结果

function sumNumbers(root) {
    function dfs(root, pretotal) {
        if (!root) {
            return 0
        }
        let total = pretotal * 10 + root.val
        if (!root.left && !root.right) {
            return total
        }
        return dfs(root.left, total) + dfs(root.right, total)
    }
    return dfs(root, 0)
}

const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
    },
    right: {
        val: 6,
    },
};

console.log(sumNumbers(root));

function sumNumbers2(root) {
    let sum = 0
    function dfs(root, val) {
        if (!root) {
            return
        }
        let curVal = Number(`${val}${root.val}`)
        if (!root.left && !root.right) {
            sum += curVal
            return
        }
        dfs(root.left, curVal)
        dfs(root.right, curVal)
    }

    dfs(root, '')
    return sum
}

console.log(sumNumbers2(root));